0791. 自定义字符串排序【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 自定义排序

1. 📝 题目描述

• leetcode

给定两个字符串 order 和 s。order 的所有字母都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回满足这个性质的 s 的任意一种排列。

---

示例 1：

输入: order = "cba", s = "abcd"
输出: "cbad"

解释:
"a"、"b"、"c"是按顺序出现的，所以"a"、"b"、"c"的顺序应该是"c"、"b"、"a"。
因为"d"不是按顺序出现的，所以它可以在返回的字符串中的任何位置。
"dcba"、"cdba"、"cbda"也是有效的输出。

示例 2：

输入: order = "cbafg", s = "abcd"
输出: "cbad"

解释：
字符 "b"、"c" 和 "a" 规定了 s 中字符的顺序。s 中的字符 "d" 没有在 order 中出现，所以它的位置是弹性的。
按照出现的顺序，s 中的 "b"、"c"、"a" 应排列为"b"、"c"、"a"。"d" 可以放在任何位置，因为它没有按顺序排列。
输出 "bcad" 遵循这一规则。
其他排序如 "dbca" 或 "bcda" 也是有效的，只要维持 "b"、"c"、"a" 的顺序。

---

提示：

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

2. 🎯 s.1 - 自定义排序

c

int rank[26];

int cmp(const void* a, const void* b) {
    return rank[*(char*)a - 'a'] - rank[*(char*)b - 'a'];
}

char* customSortString(char* order, char* s) {
    for (int i = 0; i < 26; i++) rank[i] = 26;
    for (int i = 0; order[i]; i++) rank[order[i] - 'a'] = i;
    int n = strlen(s);
    char* res = (char*)malloc(n + 1);
    memcpy(res, s, n + 1);
    qsort(res, n, sizeof(char), cmp);
    return res;
}

js

/**
 * @param {string} order
 * @param {string} s
 * @return {string}
 */
var customSortString = function (order, s) {
  const rank = new Array(26).fill(26)
  for (let i = 0; i < order.length; i++) rank[order.charCodeAt(i) - 97] = i
  return [...s]
    .sort((a, b) => rank[a.charCodeAt(0) - 97] - rank[b.charCodeAt(0) - 97])
    .join('')
}

py

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        rank = {c: i for i, c in enumerate(order)}
        return ''.join(sorted(s, key=lambda c: rank.get(c, 26)))

• 时间复杂度：$O(n\log n)$，其中 n 是字符串 s 的长度
• 空间复杂度：$O(n)$

算法思路：

• 根据 order 中字符的出现顺序建立排序优先级
• 对 s 中的字符按优先级排序，未在 order 中出现的字符置于末尾